package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 12/29/20 10:57 AM
 *
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/
 */
public class _122_买卖股票的最佳时机_II {

    public int maxProfit(int[] prices) {

        if (prices == null || prices.length <= 1) {

            return 0;
        }

        int noShares = 0,havaShares = -prices[0];

        for (int i = 0; i < prices.length; i++) {

            noShares = Math.max(noShares,havaShares + prices[i]);
            havaShares = Math.max(havaShares,noShares - prices[i]);
        }


        return noShares;
    }

    public int maxProfit01(int[] prices) {

        if (prices == null || prices.length <= 1) {

            return 0;
        }



        //7, 1, 5, 3, 6, 4

        int[] noShares = new int[prices.length];
        int[] haveSahres = new int[prices.length];

        noShares[0] = 0;
        haveSahres[0] = -prices[0];
        for (int i = 1; i < prices.length; i++) {

            noShares[i] = Math.max(noShares[i-1],haveSahres[i-1]+prices[i]);
            // -7 -1
            haveSahres[i] = Math.max(haveSahres[i - 1],noShares[i-1] - prices[i]);
        }

        System.out.println(Arrays.toString(noShares));
        System.out.println(Arrays.toString(haveSahres));


        return noShares[prices.length - 1];
    }
}
